package com.example.springbootdemo.text;

/**
 * 基于字符串编辑距离（Levenshtein Distance）
 * 编辑距离是指通过插入、删除或替换操作将一个字符串转换成另一个字符串所需的最少步骤数。这是一种衡量两个字符串相似程度的有效方式。
 */
public class LevenshteinDistance {
    public static int compute(String s, String t) {
        int[][] distance = new int[s.length() + 1][t.length() + 1];

        for (int i = 0; i <= s.length(); i++) {
            distance[i][0] = i;
        }
        for (int j = 0; j <= t.length(); j++) {
            distance[0][j] = j;
        }

        for (int i = 1; i <= s.length(); i++) {
            for (int j = 1; j <= t.length(); j++) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    distance[i][j] = distance[i - 1][j - 1];
                } else {
                    distance[i][j] = Math.min(Math.min(distance[i - 1][j], distance[i][j - 1]), distance[i - 1][j - 1]) + 1;
                }
            }
        }

        return distance[s.length()][t.length()];
    }

    public static void main(String[] args) {
        System.out.println(compute("kitten", "sitting")); // 输出: 3
    }
}